Packet based communication networks include nodes which perform various tasks on the packets passing on the network. These tasks include, for example, firewall access control, traffic routing, QoS (Quality of Service) implementation and traffic probing. As different packets are handled differently, network nodes generally employ a rule engine which is configured with rules for handling packets. Each rule identifies a group of packets and indicates the handling to be applied to that group of packets. Packets received by the node are compared to the rules until a match is found and then the handling indicated by the matching rule is applied to the packet and generally to all subsequent packets belonging to the same session (referred to herein also as a packet connection).
When a rule engine needs to apply a large number of rules, its performance may suffer due to the time needed in order to check all the rules, the amount of memory required and the increasing number of memory accesses, which are relatively slow operations.
U.S. Pat. No. 7,139,837 to Parekh et al. describes a rule engine which traverses a mesh having path nodes and path edges arranged in a tree part and graph part. The rule engine manages session entries for packets, such that the rule checking performed for a first packet of a session can be used to speed up the handling of further packets belonging to the session.
U.S. Pat. No. 6,857,018 to Jiang describes using a multiple dimension spatial indexing and mapping to speed up rule lookup in a table.
U.S. Pat. No. 8,005,945 to Cohen et al. describes adjusting the rules to segregate their ranges and minimize the number of rules.
A paper titled: “Deep Packet Inspection using Parallel Bloom Filters”, by Sarang Dharmapurikar, Praveen Krishnamurthy Todd Sproull and John Lockwood, Hot Interconnects 11, IEEE Computer Society, pp. 52-61, January 2004, suggests using Bloom filters to identify packets that potentially include predefined strings in their payload and then using an independent process to eliminate false positives.
A paper titled: “Fast Pattern-Matching Techniques for Packet Filtering, by Alok S. Tongaonkar, Master of Science in Computer Science, Stony Brook University, May 2004, describes applying techniques for pattern matching in packet filtering systems.
A paper titled “Packet Classification for Core Routers: Is there an Alternative to CAMs?”, by Florin Baboescu, Sumeet Singh, George Varghese, IEEE Infocom, 2003, suggests filtering packets using a two dimensional filter on the IP source and destination addresses at a first step and then searching through the received results.
U.S. patent publication 2011/0102157 to Tarkoma describes using a Bloom filter to filter out packets that should not be sent to a receiver.
U.S. patent 2010/0195653 to Jacobson describes packet routing using a longest-prefix-match lookup engine which may be implemented using a TCAM, tree structure or Bloom filter.
U.S. patent publication 2009/0182867 to Milliken et al. describes a method of identifying malicious packets by comparing results of applying a hash function to packets with previously generated hash results of the malicious packets.